package main

// 438. 找到字符串中所有字母异位词
func main() {
	s, p := "cbaebabacd", "abc"
	res := findAnagrams(s, p)
	for _, r := range res {
		print(r, " ")
	}
}

func findAnagrams(s string, p string) []int {
	// 题解：
	// 使用字符数组来判断相等
	// 先存储p的字符数组出现情况
	// 再用时间窗口处理s的字符，以此判断是否相等
	var res []int
	sCount, pCount := [26]int{}, [26]int{}

	if len(s) < len(p) {
		return res
	}

	for idx, lp := range p {
		pCount[lp-'a']++
		sCount[s[idx]-'a']++
	}

	if pCount == sCount {
		res = append(res, 0)
	}

	for i := 0; i < len(s)-len(p); i++ {
		sCount[s[i]-'a']--
		sCount[s[i+len(p)]-'a']++

		if sCount == pCount {
			res = append(res, i+1)
		}
	}

	return res
}

//给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
//
//异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
//
//示例 1:
//
//输入: s = "cbaebabacd", p = "abc"
//输出: [0,6]
//解释:
//起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
//起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
// 示例 2:
//
//输入: s = "abab", p = "ab"
//输出: [0,1,2]
//解释:
//起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
//起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
//起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
//
//
//提示:
//
//1 <= s.length, p.length <= 3 * 104
//s 和 p 仅包含小写字母
